/*
 * @lc app=leetcode.cn id=2115 lang=typescript
 *
 * [2115] 从给定原材料中找到所有可以做出的菜
 */

// @lc code=start
function findAllRecipes(recipes: string[], ingredients: string[][], supplies: string[]): string[] {
  // 原材料数量发生变化，更新对应数据
  const updateGraph = (supply: string): void => {
    if (graph.has(supply)) {
      const supplyGraph = graph.get(supply);
      for (const x of supplyGraph) {
        if (indeg.has(x)) {
          // 菜谱需要的材料数量减少1
          indeg.set(x, indeg.get(x) - 1);
          // 当前菜谱可以制作，形成新的原材料
          if (indeg.get(x) == 0) updateGraph(x);
        }
      }
    }
  };

  // 图的入度，表示菜需要的材料数量，如果材料数量为0，则表示可以做出菜
  const indeg = new Map<string, number>();
  // 原材料和菜谱的映射关系
  const graph = new Map<string, Set<string>>();
  // 初始化图
  for (const [i, recipe] of recipes.entries()) {
    indeg.set(recipe, ingredients[i].length);
    for (const x of ingredients[i]) {
      if (!graph.has(x)) {
        graph.set(x, new Set());
      }
      graph.get(x).add(recipe);
    }
  }

  // 遍历supplies,更新数据
  for (const supply of supplies) {
    // 直接提供的材料就是菜
    if (indeg.has(supply)) {
      indeg.set(supply, 0);
    }
    // 使用提供的材料，取更新图
    updateGraph(supply);
  }

  // 计算结果，菜中入度为0的表示材料都齐全，可以制作
  const ans = [];
  for (const [recipe, count] of indeg.entries()) {
    if (count === 0) ans.push(recipe);
  }

  return ans;
}
// @lc code=end
